package labuladong.开篇;

import leetcode.ListNode;

import java.util.List;

public class 双指针 {

    /**
     * 判断链表是否含有环
     * @param head
     * @return
     */
    public static boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (slow!=null && fast.next!=null) {
            if (slow == fast) return true;
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

    /**
     * 寻找环的起点
     * @param head
     * @return
     */
    public static ListNode getCycleStart(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (slow!=null && fast.next!=null) {
            if(slow == fast) break;
            slow = slow.next;
            fast = fast.next;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    /**
     * 寻找链表中点
     * @param head
     * @return
     */
    public static ListNode findMiddleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast!=null && fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 寻找链表倒数第K个结点
     * @param head
     * @return
     */
    public static ListNode findKNode(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;
        while (k-- > 0) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
